class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

    def __str__(self):
        return f"<Node {self.data}>"


class LinkedList:
    def __init__(self):
        self.head = None
        self.end = None

    def append(self, node, add_to_head=False):
        """
        end代表最后一个节点
        1.当前没有节点: head -> node
        2.尾部添加: end.next -> node
        3.头部添加: node.next -> head, head -> node
        :return:
        """
        if not self.head:
            self.head = node
            self.end = node
        elif add_to_head:
            node.next = self.head
            self.head = node
        else:
            self.end.next = node
            self.end = node

    def remove(self, node):
        """
        1. 移除的节点在中间: cur.next -> None, cur.prev.next -> cur.next
        2. 移除的是头节点: head -> cur.next, cur.next -> None
        3. 移除的是尾节点: cur.next本身指向就是None, 所以和1一致
        :param node:
        :return:
        """
        cur = self.head
        prev = None
        while cur:
            if cur.data == node.data:
                # 判断是否移除的是头节点
                if prev is None:
                    self.head = cur.next
                    cur.next = None
                else:
                    prev.next = cur.next
                    cur.next = None
                return
            prev = cur
            cur = cur.next

    def insert(self, index, node):
        """
        l.insert 在index的左边插入值, 其实就是在index-1的右边插入值.
        1. 插入的是中间节点: node.next -> cur.next, cur.next -> node
        2. 插入的是一个头节点: node.next -> head, head -> node
        :param index:
        :param node:
        :return:
        """
        cur = self.head
        if index == 0:
            node.next = self.head
            self.head = node
            return
        # 遍历完之后的cur就是需要在右侧插入节点的节点
        for i in range(index-1):
            cur = cur.next
            if cur is None:
                raise IndexError("LinkedList insert node exceed max length")

        node.next, cur.next = cur.next, node

    def reverse(self):
        """
        1. 中间节点: cur.next -> prev
        2. 头节点: head -> None, cur.next -> prev
        3. 尾节点: head -> cur(end), cur.next -> prev
        :return:
        """
        # 判断当前节点是否为1或者None
        if self.head and self.head.next:
            cur = self.head.next
            prev = self.head
            self.head.next = None
            while cur:
                # 三个变量都需要进行重新赋值, 所以引入中间变量next
                next = cur.next
                cur.next = prev

                prev = cur
                cur = next
            # 链表已经被反转, 那么head应该指向原本链表的尾结点
            self.head = prev
        else:
            return

    def __str__(self):
        """
        不知道当前链表的长度, 所以我们使用while
        :return:
        """
        cur = self.head
        result = ""
        while cur:
            result += str(cur) + "\t"
            cur = cur.next
        return result

    def __getitem__(self, y):
        cur = self.head
        for i in range(y):
            cur = cur.next
            if not cur:
                raise IndexError("IndexError: linked_list index out of range")
        return cur


class DoubleLinkedList(LinkedList):
    def append(self, node, add_to_head=False):
        """
        相对于单链表, 我们仅需要额外考虑prev的指向问题
        :param node:
        :param add_to_head:
        :return:
        """
        if not self.head:
            self.head = node
            self.end = node
        elif add_to_head:
            node.next = self.head

            self.head.prev = node
            self.head = node
        else:
            self.end.next = node
            node.prev = self.end
            self.end = node

    def remove(self, node):
        """
        1. 移除的是中间节点: cur.next.prev -> cur.prev
        2. 移除的头节点: head.prev -> None
        3. 移除的是尾节点: cur.next -> None
        :param node:
        :return:
        """
        cur = self.head
        while cur:
            if cur.data == node.data:
                # 判断是否移除的是头节点
                if cur.prev is None:
                    self.head = cur.next
                    cur.next = None
                    self.head.prev = None
                else:
                    cur.prev.next = cur.next
                    if cur.next is None:
                        return

                    cur.next.prev = cur.prev
                    cur.next = None
                    cur.prev = None
                return
            cur = cur.next

    def insert(self, index, node):
        """
        1. 插入头节点: head.prev -> node
        2. 插入的是中间节点: node.prev -> cur
        :param index:
        :param node:
        :return:
        """
        cur = self.head
        if index == 0:
            node.next = self.head
            self.head.prev = node
            self.head = node
            return
        # 遍历完之后的cur就是需要在右侧插入节点的节点
        for i in range(index - 1):
            cur = cur.next
            if cur is None:
                raise IndexError("LinkedList insert node exceed max length")

        node.next = cur.next
        node.prev = cur

        cur.next = node

    def reverse(self):
        """

        :return:
        """
        # 判断当前节点是否为1或者None
        if self.head and self.head.next:
            cur = self.head.next
            prev = self.head

            self.head.prev = cur
            self.head.next = None
            while cur:
                # 三个变量都需要进行重新赋值, 所以引入中间变量next
                next = cur.next
                cur.prev = cur.next
                cur.next = prev

                prev = cur
                cur = next
            # 链表已经被反转, 那么head应该指向原本链表的尾结点
            self.head = prev
            self.head.prev = None
        else:
            return


if __name__ == "__main__":
    linked_list = DoubleLinkedList()

    node_1 = Node(10)
    node_2 = Node(20)
    node_3 = Node(30)
    node_4 = Node(40)
    node_5 = Node(15)

    linked_list.append(node_1)
    linked_list.append(node_2)
    linked_list.append(node_3)
    linked_list.append(node_4)
    linked_list.remove(node_2)
    print(linked_list)
    linked_list.insert(1, node_5)
    #
    print(linked_list)
    print(linked_list.reverse())
    print(linked_list)